1. Technical Field
The present invention relates to image segmentation, and more particularly, to multi-label image segmentation of digital photographs.
2. Discussion of the Related Art
Image segmentation is commonly used, for example, in automatic or semi-automatic image analysis techniques. In such techniques, image segmentation is used to partition a digital image into disjoint connected sets of pixels, each of which corresponds to an object or region before image content can be analyzed, identified, or classified into different groups.
One popular use of image segmentation is in digital photograph editing, where it is often desirable to define a boundary between a main object and background (or between multiple objects) in the photograph. After the photograph is segmented, segments may be extracted from the original photograph, transplanted between photographs, duplicated, modified and edited in various ways.
A variety of methods for image segmentation exist such as: classification-based methods (e.g., thresholding, or multi-dimensional clustering/classification), which use information about a pixel and/or its neighborhood to classify the pixel into one of many segments; edge-based methods (e.g., edge finding and linking), which segment an image based on spatial discontinuity or edge detection; region-based methods (e.g., region growing), which segment an image based on spatial similarity amongst pixels; shape-based methods (e.g., mathematical morphology or template matching), which segment an image based on knowledge of the shape of the object to be segmented; and hybrid methods, which are a combination of one or more of the above methods.
Currently, there exist automatic and semi-automatic techniques for image analysis using various image segmentation techniques. In particular, automatic techniques such as Bayesian methods, normalized cuts, or watersheds typically operate by defining K-way clustering heuristics over image values or values derived from other processes (e.g., spectral coefficients). In an effort to address multi-label segmentation (i.e., an image segmentation technique that simultaneously finds multiple segmentation targets) without resorting to recursively applied binary segmentation, some of these methods attempt to cluster an image into K clusters with either a pre-defined K or a K chosen to satisfy a given criteria. As these are fully automatic methods, there is no user interaction. In addition, the spectral methods are not guaranteed to produce a unique solution and, in some cases, lead to a fully degenerate problem.
Some semi-automatic methods such as graph cuts, marker-based watershed, or region competition have attempted to address multi-label segmentation without resorting to recursively applying binary segmentation. For example, graph cuts does this by finding cuts with a smallest value (as defined by image gradients) that separate each labeled region from all others using 2-way graph cuts. However, extension of this method to K-way partitioning is difficult (for K>2). In addition, this method suffers from the production of segments that minimally encircle user-specified seeds if enough seeds are not placed. Similarly, a machine learning algorithm using Gaussian fields and harmonic functions finds clusters based on harmonic functions using boundary conditions set by a few known points. This algorithm, however, employs methods for similarity measures between points in feature space that are not entirely appropriate for computer vision.
Accordingly, there is a need for a multi-label image segmentation technique that is independent of modality, prior knowledge, and segmentation task, and that allows rapid and easy segmentation of digital photographs.